#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define OK        0
#define ERR       -1

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 冒泡 */
int bubbleSort(int *nums, int numSize) {
    if (!nums) return ERR;
    for (int i = 0; i < numSize; i++) {
        for (int j = i + 1; j < numSize; j++) {
            if (nums[j] < nums[i]) {
                swap(&nums[j], &nums[i]);
            }
        }
    }
    return OK;
}

/* 选择排序 */
int selectSort(int *nums, int numSize) {
    if (!nums) return ERR;
    for (int i = 0; i < numSize; i++) {
        int tmp = i;
        for (int j = i + 1; j < numSize; j++) {
            if (nums[j] < nums[tmp]) {
                tmp = j;
            }
        }
        swap(&nums[tmp], &nums[i]);
    }
    return OK;
}

/* 插入排序 */
int insertSort(int *nums, int numSize) {
    if (!nums) return ERR;
    if (numSize <= 1) return OK;
    for (int i = 1; i < numSize; i++) {
        /*
            while () {

            }
        */
        swap(&nums[i], &nums[i]);
    }
    return OK;
}

/* 快排 */
int quickSort(int *nums, int left, int right) {
    if (left >= right) return OK;
    int low = left + 1, high = right;
    while (low <= high) {
        if (nums[low] > nums[left]) {
            swap(&nums[low], &nums[high]);
            high--;
        } else {
            low++;
        }
    }
    low--;
    swap(&nums[low], &nums[left]);
    quickSort(nums, left, low - 1);
    quickSort(nums, high + 1, right);
    return OK;
}

/* 归并排序 */
int mergeSort(int *nums, int numSize) {
    
    return OK;
}

/* 桶排序 */
int bktSort(int *nums, int numSize) {
    int _max = INT_MIN, _min = INT_MAX;
    for (int i = 0; i < numSize; i++) {
        _max = MAX(_max, nums[i]);
        _min = MIN(_min, nums[i]);
    }
    /* 映射桶, C99支持动态数组，不用malloc，该处有问题 */
    int *buket = (int *)malloc(sizeof(int) * (_max - _min + 1)); 
    memset(buket, 0, sizeof(int) * (_max - _min + 1));
    /* 将数据映射，放入桶内 */
    for (int i = 0; i < numSize; i++) {
        buket[nums[i] - _min]++;
    }

    for (int i = 0, j = 0; i < _max - _min + 1; i++) {
        while (buket[i] > 0) {
            nums[j++] = i + _min;
            buket[i]--;
        }
    }
    free(buket);
    return OK;
}

/* 堆排序 */
int heapSort(int *nums, int numSize) {
    return OK;
}

/* 希尔排序 */
int shellSort(int *nums, int numSize) {
    return OK;
}

/* 计数排序 */
int countSort(int *nums, int numSize) {
    return OK;
}

/* 基数排序 */
int radixSort(int *nums, int numSize) {
    return OK;
}

/* 混合并优化后的排序算法 */
int timSort(int *nums, int numSize) {
    return OK;
}

/* 睡眠排序 */
int sleepSort(int *nums, int numSize) {
    return OK;
}

int main() {
    int nums[10] = {0,2,5,4,87,1,20,47,1,12};
    bubbleSort(nums, 10);
    for (int i = 0; i < 10; i++) {
        printf("%d,", nums[i]);
    }
    int a = 0;
    scanf("%d", &a);
    return OK;
}